/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-04 21:35:56
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-06 20:11:06
 * @FilePath: \LeetCode\78.子集.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=78 lang=cpp
 *
 * [78] 子集
 *
 * 方法1：利用子集树得到所有情况
 * - 注意：把与递归无关的变量都设为全局变量 std::vector<int> n;
 *
 * 方法2（官方题解）：位运算操作
 */

#include <vector>
#include <iostream>

// @lc code=start
class Solution
{
public:
    std::vector<std::vector<int>> result;
    std::vector<int> n;
    int len;

    void visitSubTree(const std::vector<int> &nums, int i)
    {
        if (i == len)
        {
            result.push_back(n);
        }
        else
        {
            /* 左子树 */
            n.push_back(nums[i]);
            visitSubTree(nums, i + 1);
            /* 右子树 */
            n.pop_back();
            visitSubTree(nums, i + 1);
        }
    }

    std::vector<std::vector<int>> subsets(std::vector<int> &nums)
    {
        len = nums.size();
        // visitSubTree(nums, 0);

        for (int mask = 0; mask < (1 << len); mask++) // (1 << n) = 2^n
        {
            n.clear();
            for (int i = 0; i < len; i++)
            {
                if (mask & (1 << i))
                    n.push_back(nums[i]);
            }
            result.push_back(n);
        }

        return result;
    }
};
// @lc code=end
